#include <iomanip>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

const int kMaxM = 120;
const int kInf = 1e9;

int colors[kMaxM][kMaxM], ids[kMaxM][kMaxM];
vector<pair<int, int>> g[kMaxM * kMaxM * 4];
int dis[kMaxM * kMaxM * 4];
queue<int> que[kMaxM * kMaxM];

bool Check(int x, int y, int m) {
  return x >= 0 && x < m && y >= 0 && y < m && colors[x][y] != 0;
}

void AddEdge(int u, int v, int costuv, int costvu) {
  // cout << u << "-->" << v << ": " << costuv << endl;
  g[u].emplace_back(v, costuv);
  // cout << v << "-->" << u << ": " << costvu << endl;
  g[v].emplace_back(u, costvu);
}

vector<int> BuildGraph(int m) {
  int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  int tot = 0;
  vector<int> end_pos;

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      if (colors[i][j] == 0) {
        continue;
      }
      ids[i][j] = tot++;

      if (Check(i - 1, j, m)) {
        int cost = colors[i][j] != colors[i - 1][j];
        AddEdge(ids[i][j], ids[i - 1][j], cost, cost);
      }
      if (Check(i, j - 1, m)) {
        int cost = colors[i][j] != colors[i][j - 1];
        AddEdge(ids[i][j], ids[i][j - 1], cost, cost);
      }
      if (i == m - 1 && j == m - 1) {
        end_pos.emplace_back(ids[m - 1][m - 1]);
      }
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      if (colors[i][j] != 0) {
        continue;
      }
      unordered_map<int, int> c_m;
      int cnt = 0;

      for (int k = 0; k < 4; k++) {
        if (Check(i + dir[k][0], j + dir[k][1], m)) {
          int c = colors[i + dir[k][0]][j + dir[k][1]];
          if (c_m.count(c) == 0) {
            c_m[c] = cnt++;
          }
        }
      }

      for (int k = 0; k < 4; k++) {
        if (Check(i + dir[k][0], j + dir[k][1], m)) {
          int id = ids[i + dir[k][0]][j + dir[k][1]];
          int c = colors[i + dir[k][0]][j + dir[k][1]];

          for (const pair<int, int> &state : c_m) {
            int cost = c != state.first;
            AddEdge(id, state.second + tot, 2 + cost, cost);
          }
        }
      }

      if (i == m - 1 && j == m - 1) {
        for (int k = 0; k < cnt; k++)
          end_pos.emplace_back(tot + k);
      }

      tot += cnt;
    }
  }

  fill(dis, dis + tot, kInf);
  return end_pos;
}

int BFS(int m, vector<int> end_pos) {
  if (end_pos.empty()) {
    return -1;
  }
  dis[0] = 0;
  que[dis[0]].emplace(0);

  for (int d = 0; que[d].size() + que[d + 1].size() + que[d + 2].size() + que[d + 3].size(); d++) {
    for (; !que[d].empty(); que[d].pop()) {
      int now = que[d].front();

      if (dis[now] != d) {
        continue;
      }
      for (const pair<int, int> &edge : g[now]) {
        if (dis[edge.first] > dis[now] + edge.second) {
          dis[edge.first] = dis[now] + edge.second;
          que[dis[edge.first]].emplace(edge.first);
        }
      }
    }
  }

  int ret = dis[end_pos[0]];
  for (int pos : end_pos) {
    ret = min(ret, dis[pos]);
  }
  // cout << "Dist:" << endl;
  // for (int i = 0; i < 21; i++) {
  //   cout << dis[i] << endl;
  // }
  return ret == kInf ? -1 : ret;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  // freopen("3956.in", "r", stdin);
  // freopen("3956.out", "w", stdout);
  int m, n;

  cin >> m >> n;
  for (int i = 0; i < n; i++) {
    int x, y, c;

    cin >> x >> y >> c;
    colors[x - 1][y - 1] = c + 1;
  }
  vector<int> end_pos = BuildGraph(m);
  cout << BFS(m, end_pos) << "\n";
  return 0;
}